package cn.lbd.arithmetic.sort;

import org.junit.Test;

public class ShellSort {
    private static void sort(int[] array) {
        int count = 0;
        for (int n = array.length/2; n >=1 ; n/=2) {
            for (int i = n; i < array.length; i++) {
                int value = array[i];
                int index = i-n;
                while(index>=0 && value < array[index]){
                    array[index+n] = array[index];
                    index-=n;
                }
                array[index+n]=value;
            }
            //System.out.println("第"+(++count)+"次希尔排序"+Arrays.toString(array));
        }
    }


    public static void main(String[] args) {
        int[] array={8,9,1,7,2,3,5,4,6,0};
        sort(array);
    }


    //800W数据1.809
    @Test
    public void batchTest(){
        int[] arr = new int[8000000];
        for(int i =0; i < 8000000;i++) {
            arr[i] = (int)(Math.random() * 8000000);
        }

        long start = System.currentTimeMillis();

        sort(arr);

        long end = System.currentTimeMillis();

        System.out.println((double)(end-start)/1000);
    }
}
